package 栈与队列;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 239. 滑动窗口最大值
 * 分析思路：
    给定一个数组 nums 和一个整数 k，k 表示滑动窗口的大小。窗口会从数组的最左边滑动到最右边，每次移动一位，你需要找出每个窗口位置时的最大值。
    我们可以采用双端队列来模拟窗口。
    为什么双端队列，双端队列可以从两边操作，可以快速地弹出队首和队尾元素。在这个问题中，我们用它来维护当前窗口内最有潜力成为最大值的元素的索引，
 这样做的目的是确保：
    - 队列的第一个元素是当前窗口的最大值；
    - 队列中的元素是递减的，即从头到尾部的元素都是递减的
    解题思路：
    1、初始化: 创建一个双端队列deque， 来保存有潜力成为窗口最大值的元素的索引。 创建一个result数组，存储每个窗口的最大值。
    2: 遍历数组：
       对于数组中的每个元素，我们将进行如下操作;
        a.维护队列的大小：确保队列中存储的都是当前窗口内的元素，这通过比较当前元素的索引i和队列头部的索引来完成，如果头部元素的索引小于i-k+1（即当前元素减去窗口大小），
    这就意味着头部元素已经不在当前窗口中，需要将其移除。
        b. 维护队列的顺序: 我们需要确保队列是按照元素递减排序的，以保证队列头部始终是当前窗口的最大值，当新的元素大于队尾元素时，队尾元素就不再有机会称为后续窗口的最大值了，
    因此我们需要将它移除，直到队列为空，或者新的元素小于队尾元素为止。
        c. 将当前元素的索引添加到队列中，经过上述步骤，将当前元素的索引放到队列尾部。
        d. 更新结果数组，当我们遍历到第K个元素及以后的元素时（数组从K-1索引开始）， 每个窗口的最大值就是队列头部的元素，将这个值添加到result中。
   3: 返回结果数组。

 总结： 滑动窗口的解题核心就是利用双端队列与队首元素始终为最大值的规则实现
 * @Author lf
 * @Date 3/28/2024
 */
public class MaxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        // 定义双端队列, 队首元素永远为最大值，此队列元素是递减的
        Deque<Integer> deque = new ArrayDeque<>();
        // 定义结果数组
        int [] res = new int[nums.length - k +1];
        int ri =0; //定义数组的索引

        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 维护队列的大小, 队首元素与当前元素索引比较，如果队首索引小于i - k +1 ，则证明队首元素已经不在当前窗口中了，需要移除
            while (deque.size() > 0 && deque.peek() < i - k +1){
                deque.poll();
            }
            // 维护队列的顺序，递减队列保证队首元素最大，如果当前元素大于队尾元素，则队尾元素将永远不会是后续窗口的最大值了，需要移除，知道队列为空或者新的元素小于队尾元素
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]){
                // 移除队尾元素
                deque.pollLast();
            }
            // 将当前元素的索引加入到队尾中
            deque.offer(i);
            // 如果当前索引大于等于K-1，则后续遍历每一位都会有一个滑动数组,将队首最大值存放到result数组
            if(i >= k-1 ){
                res[ri++] = nums[deque.peek()];
            }
        }

        return res;
    }

    public static void main(String[] args) {
        MaxSlidingWindow solution = new MaxSlidingWindow();
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] result = solution.maxSlidingWindow(nums, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}
